#include <myheader_c_plus.h>
#include <map>
#include <unordered_map>
#include <deque>
#include <unordered_map>
using std::endl;
using std::cout;
using std::pair;
using std::list;
using std::deque;
using std::unordered_map;

class LRUCache{

public:
    //construct
    LRUCache(int capacity)
    :_capacity(capacity)
    {

    }


    //get
    int get(int key)
    {
        auto it = _cacheMap.find(key);
        if(it == _cacheMap.end()){
            return -1;
        }
        int value = it->second->second;
        cout << "32 value:" << value << endl;
        cache_list.erase(it->second);
        cache_list.push_front({key, value});
        _cacheMap[key] = cache_list.begin();
        return value;
    }


    void put(int key, int value){
        auto it = _cacheMap.find(key);
        if(it != _cacheMap.end())
        {
            auto node = it->second;
            cache_list.erase(node);

        }
        else
        {
            if(cache_list.size() == _capacity){
                //需要踢出
                auto it = cache_list.end();
                it--;
                auto it2 = _cacheMap.find(it->first);
                _cacheMap.erase(it2);
                cache_list.erase(it);
            }
        }
        //插入节点到头
        cache_list.push_front({key, value});
        _cacheMap[key] = cache_list.begin();
    }


private:
    list<pair<int, int>> cache_list;
    unordered_map<int,list<pair<int, int>>::iterator> _cacheMap;
    size_t _capacity;
    
    
};
int main(int argc, char *argv[])
{
    LRUCache lru(2);
    lru.put(1,1);
    lru.put(2,2);
    cout << lru.get(1) << endl;
    lru.put(3,3);
    cout << lru.get(2) << endl;
    lru.put(4,4);
    cout << lru.get(1) << endl;
    cout << lru.get(3) << endl;
    cout << lru.get(4) << endl;
    
    
    return 0;
}

